package org.wuxinshui.boosters.nowcoder.classicQuestion;

import java.util.ArrayList;

/**
 * 描述
 * <p>
 * 求给定的二叉树的前序遍历。
 * 例如：
 * 给定的二叉树为{1,#,2,3},
 * <p>
 * 返回：[1,2,3].
 * 备注；用递归来解这道题很简单，你可以给出迭代的解法么？
 * 如果你不明白{1,#,2,3}的含义，点击查看相关信息
 * <p>
 * 示例1:
 * 输入：{1,#,2,3}
 * 返回值：[1,2,3]
 */
public class CC7PreorderTraversal {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList
     */
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write code here
        ArrayList<Integer> result = new ArrayList();

        preorderHelper(root, result);

        return result;

    }

    public void preorderHelper(TreeNode node, ArrayList<Integer> result) {
        if (null == node) {
            return;
        }

        result.add(node.val);
        preorderHelper(node.left, result);
        preorderHelper(node.right, result);
    }

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    }
}
